패턴 매칭

텍스트 스트링에서 원하는 문자 패턴을 찾아 내는 것
패턴 기술
1. 접합(concatenation)
  - 패턴에서 인접해 있는 두 문자가 텍스트에서 나타나면 매치
2. 논리합(or)
  - 두개의 문자 중 하나가 텍스트에 나타나면 매치
3. 폐포(closure)
  - 특정한 문자가 0개 이상 나타나면 매치합니다.

패턴매칭 방법들중 비결정적 알고리즘(Non-deterministic algorithms)을 사용한 방법을 적어보겠습니다.
비결정적 알고리즘이란 알고리즘 분류 방법들 중 결정적 혹은 비결정적 (Deterministic or non-deterministic)에 따라서 분류 하는 방법을 의미합니다.

패턴 매칭 장치 - 결정적 장치

결정적 알고리즘(Deterministic algorithms) 각각의 상태가 다음 입력 문자로 인해서 완전하게 결정되는 것을 의미합니다. 즉, 계산의 각단계에서 단 한가지의 가능성만을 고려할 수 있는 알고리즘을 의미합니다. 결정적 알고리즘에 해당하는 문제들은 동일한 입력에 대해서 동일한 출력을 항상 가집니다. 예를들면 KMP 알고리즘이 있습니다.
하지만 우리는 이러한 문제를 가집니다. 제시된 text에서 gray와 grey를(모두 회색을 의미) 찾는것입니다. 그때 KMP 알고리즘을 두번 사용해서 gray 와 grey를 찾아야 할까요? 분명 더 좋은 방법이 있을겁니다. 그래서 고안된 방법이 정규표현식을 사용한 방법입니다.

패턴 매칭 장치 - 비결정적 장치

비결정적 알고리즘(Non-deterministic algorithms)은 결정적 알고리즘과 다르게 동일한 입력에 대해 매 순간에 동일한 행동을 취하지 않습니다. 매 순간마다 추측을 통해서 해결함을 볼 수 잇습니다.

결정문제로서의 분류 (P | NP)

결정문제란 어떤 문제의 해답이 ‘예’ or ‘아니오’로 대답이 가능한 모든 문제를 의미합니다. 예를 들어 36은 6으로 나누어 떨어지는가? 는 결정문제에 해당합니다. P문제 (Polynomial)의 경우 결정문제중 비교적 쉽게 계산이 가능한 문제들을 의미합니다. 대표적으로 quick sort를 제외한 정렬들이 있습니다. NP문제(Non-deterministic Polynomial)의 경우 결정 문제들 중에서 검산이 가능한 문제들을 의미합니다. 예를 들어 어떤 결정문제에 대해서 답이 분명히 있으며, 답에 대한 해답을 완벽하게 설명가능한 방법이 있는경우 이 방법을 통해 검산이 가능합니다. np문제의 예시를 보겠습니다.

{1,5,7 ,-9, -22, -200, 10 , 6}에서 부분집합을 만들때 그 부분집합의 원소들의 합이 0이 되도록 하는 집합이 있는가?

아직 컴퓨터 과학이론에서 이러한 부분집합에 대해서 모든경우의 수를 확인하는(brute force)방법이 아니라면 정확한 정답을 확인할 수 있는 알고리즘 이론이 없습니다.
하지만 어느 누군가가 {1 ,5 ,7, -22 , 6}의 합은 0이야! 라고 말해준다면 우리는 어렵지 않게 해당하는 문제가 Yes 라는 것을 어렵지 않게 도출할 수 있습니다. 즉 이 문제는 NP문제지만 P문제인지는 증명할 수 없는 상태입니다.

+) P와 NP문제에 대해 의미 있는 토론들이 다수 있습니다. P=NP인가? 라는 문제는 유명한 수학의 7대 난제중 하나입니다.

정규식

정규 표현식, 또는 정규식은 문자열에서 특정 문자 조합을 찾기 위한 패턴입니다. JavaScript에서는 정규 표현식도 객체로서, RegExp의 exec()와 test() 메서드를 사용할 수 있습니다.

- * : 괄호 안에 있는 문자들이 0번 이상 나타남
- ? : 어떤 문자와도 매칭이 됩니다.

ex) (1+01)*(0+1) : 연속적으로 두 개의 0이 나오지 않는 0과 1로 이루어진 모든 문자열
010101 , 101101 등등

위의 비결정적 패턴장치에서 노드의 숫자들은 단순한 index일뿐 의미는 없습니다.
빈 노드는 중간 경유 지점으로서 한개의 노드에 두가지 값이 동시에 도착하는 것이 아닌 합류 지점으로서의 역할을 가지도록 합니다
끝 노드는 반드시 한개가 존재해야합니다.

현재까지 일치된 상태에서 + 기호 아래로 내려가는 시점에 매칭된 문자가 반영됩니다.

Reference

아직 배움의 단계라 정확한 정보가 아닐 수 있습니다.😂
피드백은 seoungin1228@gmail.com 으로 부탁드리겠습니다☺️